#!/usr/bin/env python
# -*- indent-tabs-mode: nil; tab-width: 4; coding: utf-8 -*-
# vi: set ts=4 sts=4 sw=4 set smarttab set expandtab
#http://www.careercup.com/question?id=14851686
#Facebook interview question
import random


def find_point_intersect_most(arr):
    points = [(interval[0], 0) for interval in arr] + [(interval[1], 1) for interval in arr]
    points.sort(key = lambda x: x[0])
    max_occu, occu, position = 0, 0, -1
    for point in points:
        if point[1]: occu -= 1
        else: occu += 1
        if occu > max_occu:
            max_occu = occu
            position = point[0]
    return max_occu, position

if __name__ == '__main__':
    for i in range(0, 20):
        length = random.randint(10, 20)
        arr = []
        for j in range(0, length):
            start_interval = random.randint(0, 100)
            end_interval = random.randint(0, 100) + start_interval
            arr.append((start_interval, end_interval))
        print arr, find_point_intersect_most(arr)
